package main

import "fmt"

//#link: https://leetcode-cn.com/problems/permutations/
func main() {
	nums := []int{1, 2, 3}
	fmt.Println(permute(nums))
}

var result [][]int

//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
func permute(nums []int) [][]int {
	result = make([][]int, 0)
	backTrace(nums, []int(nil), make([]bool, len(nums)))
	return result
}

func backTrace(nums, path []int, used []bool) {
	if len(path) == len(nums) {
		result = append(result, append([]int(nil), path...))
		return
	}
	for i := 0; i < len(nums); i++ {
		if used[i] {
			continue
		}
		if i-1 >= 0 && nums[i-1] == nums[i] && !used[i-1] {
			continue
		}
		used[i] = true
		path = append(path, nums[i])
		backTrace(nums, path, used)
		used[i] = false
		path = path[:len(path)-1]
	}
}

func isContains(n int, nums []int) bool {
	for _, num := range nums {
		if n == num {
			return true
		}
	}
	return false
}
